#include"HuffmanTree.h"
#include<iostream>
#include<queue>
#include<unordered_map>
#include<string>
#include<vector>
#include<fstream>
#include<assert.h>
#include<stack>
#include<unordered_set>
namespace dzh
{
	
	bool Compare::operator()(pair<char, int> a, pair<char, int> b)
	{
		return a.second > b.second; 
	}

	HuffmanNode::HuffmanNode(int weight, char data, int left, int right, int parent)
		:_weight(weight)
		,_left(left)
		,_right(right)
		,_parent(parent)
		,_data(data)
	{
	}

	ostream& operator<<(ostream& os, const HuffmanNode& t)
	{
		os << "权重：" << t._weight << " 左孩子：" << t._left << " 右孩子：" << t._right << " 父母：" << t._parent << " 字符：" << t._data << endl;
		return os;
	}
	HuffmanTree::HuffmanTree(string filename)
		:_filename(filename)
	{
		unordered_map<char, int> m;
//		ofstream ofs(filename);
		ifstream ifs(filename, ios_base::binary | ios_base::in);
		//读取文件，并使用哈希计算每个字符出现的次数
		if(ifs.is_open())
		{
			char c = ' ';
			while (ifs.read(reinterpret_cast<char*>(&c), 1))
			{
				++_sourceCharCount;
				++m[c];
			}
		}
		else
		{
			assert(false);
		}
		ifs.close();

		//注意判断一下文件中没有数据的情况，直接停止程序
		if(m.empty())
		{
			cout << "文件中没有数据！" << endl;
			assert(false);
		}
		_uniqueCharCount = m.size();//将哈希中的size赋值给_uniqueCharCount

		//将哈希中的数据入小堆
		priority_queue<pair<char, int>, vector<pair<char, int>>, Compare> q;
		for(const auto& e : m)
		{
			q.emplace(e);
		}
		//将小堆中的数据依次存放入vector，即创建仿二叉树
		//此过程共分为两步，第一步是将创建的所有节点全部放入vector
		//第二步是为vector中的每个节点找到对应的parentnode
		
		//第一步
		while(q.size() > 1)//当堆中数据个数为1时，说明树已经创建完毕了
		{
		//	cout << q.size() << endl;
			HuffmanNode n1(q.top().second, q.top().first);
			q.pop();
			HuffmanNode n2(q.top().second, q.top().first);
			q.pop();
			pair<char, int> parentnode(' ', n1._weight + n2._weight);
			q.emplace(parentnode);
			_root.emplace_back(n1);
			_root.emplace_back(n2);
		}
		assert(!q.empty());
		_root.emplace_back(q.top().second, q.top().first);//将堆中剩下的根节点放到vector中
		q.pop();

		//第二步
		//由于上面使用优先级队列进行vector的插入，所以，现在vector中的数据应是根据weight的值进行从小到大排列的，因此，现在仅需要每次循环都依次访问两个数据
		for(size_t i = 0; _root.size() != 0 && i < _root.size() - 1; i += 2)//最先要注意的就是size==0的问题，由于返回值是size_t，所以要极力避免size == 0 && size - 1的情况
		{
			for(size_t j = i + 2; j < _root.size(); ++j)//由于vector是按照从小到大的顺序排列的，所以直接从i+2的位置开始搜索权重合适且data为空的节点
			{
				if(_root[j]._weight == _root[i]._weight + _root[i + 1]._weight && _root[j]._data == ' ' && _root[j]._left == -1 && _root[j]._right == -1)
				{
					_root[i]._parent = j;
					_root[i + 1]._parent = j;
					_root[j]._left = i;
					_root[j]._right = i + 1;
					break;
				}
			}
		}

		//建好模拟树后，开始建立编码表与反编码表
		_table.reserve(_uniqueCharCount * 4 / 3);//利用_uniqueCharCount提前扩充好哈希表（注意，一般负载因子是0.75，所以这里使用负载因子的倒数），避免后续可能的多次扩充造成的资源浪费
		_retable.reserve(_uniqueCharCount * 4 / 3);
		string codes = "";
		stack<char> sk;
		char mid = '0';
		//assert(_root.empty());
		for(size_t i = 0; i < _root.size(); ++i)
		{
			const auto& e = _root[i];
			//cout << e._data << endl;
			if(e._data != ' ')
			{
				//cout << 1 << endl;
				int child = i;
				int parent = e._parent;
				while(parent != -1)
				{
					if(&_root[(_root)[parent]._left] == &_root[child])//使用地址进行左右节点的比较，先开始使用的data进行比较，但因为中间节点的data均为' ',会导致无法正确区分，想到了可以直接使用地址进行比较
					{
						mid = '0';
					}
					else
					{
						mid = '1';
					}
			//		cout << mid << endl;
					sk.emplace(mid);
					child = parent;
					parent = _root[parent]._parent;
				}
				while(!sk.empty())
				{
					codes += sk.top();
				//	cout << sk.top();
					sk.pop();
				}
				//cout << codes << endl;
				_table.emplace(e._data, codes);
				_retable.emplace(codes, e._data);
				codes = "";
			}
		}
	}
		//使用文本形式写入01，是压缩的中间实验函数
		//void EnCode(string codeFileName)
		//{
		//	ifstream ifs(_filename, ios_base::in);
		//	ofstream ofs(codeFileName, ios_base::out);
		//	char ch = ' ';
		//	string s = "";
		//	while(ifs >> ch)
		//	{
		//		s = _table[ch];
		//		ofs << s;
		//	}
		//	ofs.close();
		//	ifs.close();
		//}

		//使用二进制形式写入01，是最终的结果函数
	void HuffmanTree::EnCode(string codeFileName)
	{
		//一个源文件可能需要被压缩成多份，因此使用哈希存储压缩文件的文件名，方便解压时判断文件是否是被该类压缩的
		_codeFileName.emplace(codeFileName);
		ifstream ifs(_filename, ios_base::binary | ios_base::in);
		ofstream ofs(codeFileName, ios_base::binary | ios_base::out);
		char ch = ' ';//用于读取源文件中的字符
		unsigned char buf = 0;//用于记录二进制位
		string s = "";
		int count = 7;//用于记录当前char未被使用的比特位数（范围为0~7）
		while (ifs.read(reinterpret_cast<char*>(&ch), 1))
		{
			s = _table[ch];
			for(const auto& e : s)
			{
				size_t bitValue = e - '0';
				buf |= (bitValue << count);
				--count;
				if(count == -1)
				{
					ofs.write(reinterpret_cast<const char*>(&buf), 1);
					buf = 0;
					count = 7;
				}
			}
		}

		//记得处理最后存储在buf中但比特位还未使用完全的数据
		if(count != 7)
		{
			ofs.write(reinterpret_cast<const char*>(&buf), 1);
		}
		ofs.close();
		ifs.close();
		cout << "压缩成功！" << endl;
	}
	void HuffmanTree::DeCode(string codeFileName, string deCodeFileName)
	{
		if(_codeFileName.find(codeFileName) == _codeFileName.end())
		{
			cout << "所解压的文件不是由当前对象压缩的！" << endl;
			return;
		}
		ifstream ifs(codeFileName, ios_base::binary | ios_base::in);
		assert(ifs.is_open());
		ofstream ofs(deCodeFileName, ios_base::out);
		char ch = ' ';//用于将转码后的字符写入文件
		unsigned char buf = 0;//用于记录二进制位
		string decodedOutput = "";//用于读取二进制中的比特位
		int count = 7;//用于记录当前已经读取完毕的比特位（范围为0~7）
		size_t num = 0;//记录成功转换的字符个数，与压缩时的总字数对比，相等则停止转换
		while (ifs.read(reinterpret_cast<char*>(&buf), 1))
		{
			while(count > -1)
			{
				if(num == _sourceCharCount)//读取到最后一个字节，可能出现bit中遇到填充用的二进制的0的情况，此时仅需break内部循环即可，因为此时已是最后一次外部循环
				{
					break;
				}
				char binNum = ((buf >> count) & 1) + '0';//这里一定注意运算符优先级问题，要把1放到小括号中，先与&运算，再+
				--count;
				decodedOutput += binNum;
				if(_retable.find(decodedOutput) != _retable.end())
				{
					ch = (_retable)[decodedOutput];
		//			cout << ch << " ";
					ofs << ch;
					ch = ' ';
					decodedOutput = "";
					++num;
				}
			}
			count = 7;
		}
		if(ifs.eof())
		{
			cout << "文件解压成功！" << endl;
		}
		else if(ifs.fail())
		{
			cout << "文件解压失败！" << endl;
		}
		else if(ifs.bad())
		{
			cout << "ifstream出现系统级错误！" << endl;
		}
		else
		{
			assert(false);
		}
	}
	void HuffmanTree::PrintTree()
	{
		for(const auto& e : _root)
		{
			cout << e << endl;
		}
	}
	void HuffmanTree::PrintTable()
	{
		for(const auto& e : _table)
		{
			cout << "字符为：" << e.first  << " 编码为：" << e.second << endl;
		}
	}
	size_t HuffmanTree::UniqueCharCount()
	{
		return _uniqueCharCount;
	}
	size_t HuffmanTree::SourceCharCount()
	{
		return _sourceCharCount;
	}

	void test1()
	{
		cout << "请输入源文件的文件名：" << endl;
		string fileName;
		cin >> fileName;
		HuffmanTree ht(fileName);
		cout << "总字符数为：" << ht.SourceCharCount() << endl;
		cout << "HuffmanTree为：" << endl;
		ht.PrintTree();
		cout << "编码表为：" << endl;
		ht.PrintTable();
		cout << "请输入压缩文件的文件名：" << endl;
		string codeFileName;
		cin >> codeFileName;
		ht.EnCode(codeFileName);
		cout << "请输入需要解压的文件的文件名以及接收解压后文件的文件名：" << endl;
		string deCodeFileName;
		cin >> codeFileName >> deCodeFileName;
		ht.DeCode(codeFileName, deCodeFileName);
	}
	void test2()
	{
		HuffmanTree ht("HuffmanTree_test.txt");
		string codeFileName;
		ht.PrintTable();
		ht.PrintTree();
		ht.EnCode("zip.txt");
		ht.DeCode("zip.txt", "yuanwenjian.txt");
	}
}
